{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #x 的平方根"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mySqrt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #x 的平方根"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非负整数 <code>x</code> ，计算并返回 <code>x</code> 的平方根，即实现&nbsp;<code>int sqrt(int x)</code>&nbsp;函数。</p>\n",
    "\n",
    "<p>正数的平方根有两个，只输出其中的正数平方根。</p>\n",
    "\n",
    "<p>如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> x = 4\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> x = 8\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>0 &lt;= x &lt;= 2<sup>31</sup>&nbsp;- 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 69&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/sqrtx/\">https://leetcode-cn.com/problems/sqrtx/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jJ0w9p](https://leetcode.cn/problems/jJ0w9p/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jJ0w9p](https://leetcode.cn/problems/jJ0w9p/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(sqrt(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x**0.5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x**0.5)\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        while i * i <= x:\n",
    "            i += 1\n",
    "        return int(i - 1)\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l, r = 0, x\n",
    "        while l <= r:\n",
    "            mid = l+(r-l)//2\n",
    "            if mid ** 2 <=x:\n",
    "                ans = mid\n",
    "                l = mid+1\n",
    "            else:\n",
    "                r = mid-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        # 这里有些二分法？\n",
    "        i = 0\n",
    "        while i*i <= x:\n",
    "            i += 1\n",
    "        return i-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l,r = 0,x\n",
    "        # 左闭右开\n",
    "        while l < r:\n",
    "            mid = (l+r)>>1\n",
    "            if mid**2 == x:\n",
    "                return mid\n",
    "            elif mid**2 < x < (mid+1)**2:\n",
    "                return mid\n",
    "            elif mid**2 > x:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l = 0\n",
    "        r = x \n",
    "        while l < r:\n",
    "            mid = l + (r-l+1)//2\n",
    "            if mid * mid <= x:\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left=0\n",
    "        right=x\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if mid**2<x:\n",
    "                left=mid+1\n",
    "            elif mid**2>x:\n",
    "                right=mid-1\n",
    "            else:\n",
    "                return mid\n",
    "        return left-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x <= 4:\n",
    "            left, right = 0, x\n",
    "        else:\n",
    "            left, right = 0, x//2\n",
    "        ans = x\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if mid*mid <= x:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                ans = mid -1\n",
    "                right = mid -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left = 0\n",
    "        right = max(x, 1)\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left - right) // 2 + right\n",
    "            if mid * mid <= x:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l, r = 0, x\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (r - l)//2 + l\n",
    "            if mid * mid <= x and (mid + 1)*(mid + 1) > x:\n",
    "                return mid\n",
    "            if mid * mid < x:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        c = x\n",
    "        x0 = x\n",
    "        while True:\n",
    "            xi = (x0 + c / x0) * 1 / 2\n",
    "            if abs (x0 - xi) < 1e-7:\n",
    "                break\n",
    "            x0 = xi\n",
    "        return int(xi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        i = int(10**(len(str(x))/2-1))\n",
    "        while i*i <=x :\n",
    "            i +=1\n",
    "        return i-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x==0:return 0\n",
    "        guess_num  = 10000\n",
    "        count  = 10000\n",
    "        for i in range(count):\n",
    "            guess_num = (guess_num+x/guess_num)*0.5\n",
    "        \n",
    "        return int(guess_num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x ** (1/2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left, right = 0, x\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid * mid == x:\n",
    "                return mid\n",
    "            elif mid * mid > x:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x==0:\n",
    "            return 0\n",
    "        for i in range(1,x+1):\n",
    "            if i*i==x:\n",
    "                return i\n",
    "            if i*i>x:\n",
    "                return i-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left, right = 0, x\n",
    "        ans = -1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid * mid <= x:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        # 二分查找\n",
    "        left = 1\n",
    "        right = x + 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if (mid**2) == x:\n",
    "                return mid\n",
    "            elif (mid**2) < x:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        res=0\n",
    "        if x<=1:\n",
    "            return x\n",
    "        for i in range(1,x):\n",
    "            if i*i<=x:\n",
    "                res=i\n",
    "            else:\n",
    "                break\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        i = x ** 0.5\n",
    "        if i < 0:\n",
    "            i = -i\n",
    "            x = int(i)\n",
    "            return x\n",
    "        else:\n",
    "            x = int(i)\n",
    "            return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left = 1\n",
    "        right = x\n",
    "        ans = 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid * mid <= x:\n",
    "                left = mid + 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l = 0\n",
    "        r = x\n",
    "        while l < r:\n",
    "            mid = l + (r - l + 1) // 2\n",
    "            if mid * mid <= x:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 1 or x == 0:\n",
    "            return x\n",
    "        \n",
    "        for i in range(1, x):\n",
    "            if i*i == x:\n",
    "                return i\n",
    "            if i*i < x and (i+1)*(i+1) > x:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0 or x == 1:\n",
    "            return x\n",
    "        \n",
    "        left, right = 1, x // 2\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            square = mid * mid\n",
    "            \n",
    "            if square <= x:\n",
    "                left = mid \n",
    "            else:\n",
    "                right = mid - 1\n",
    "                \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l,r=0,x\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if mid*mid>x:\n",
    "                r=mid\n",
    "            elif mid*mid<x:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                return mid\n",
    "        return l if l*l==x else l-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "\n",
    "        guess = x / 2\n",
    "        while abs(guess ** 2 - x) > 1e-5:\n",
    "            guess = 0.5 * (guess + x / guess)\n",
    "\n",
    "        return int(guess)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x==1:return 1\n",
    "        l, r = 0, x\n",
    "        while l < r-1:\n",
    "            mid = (l + r)//2\n",
    "            if mid*mid<x:l = mid\n",
    "            elif mid*mid>x:r = mid\n",
    "            else: return mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l=0\n",
    "        h=x\n",
    "        while l<=h:\n",
    "            mid=l+h>>1\n",
    "            if mid*mid==x:\n",
    "                return mid\n",
    "            elif mid*mid<x:\n",
    "                if (mid+1)*(mid+1)>x:\n",
    "                    return mid\n",
    "                else:\n",
    "                    l=mid+1\n",
    "            else:\n",
    "                if (mid-1)*(mid-1)<=x:\n",
    "                    return mid-1\n",
    "                else:\n",
    "                    h=mid-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        #return int(x**0.5)\n",
    "        i = 0\n",
    "        while i * i <= x:\n",
    "            i += 1\n",
    "        return int(i - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        # 妈的，最简单的实现\n",
    "        i = 0\n",
    "        while i*i <= x:\n",
    "            i += 1\n",
    "        return i-1\n",
    "\n",
    "        # 当然了，这里肯定有可以省略的步骤？\n",
    "        # 二分查找。2^10 = 1024 2^30 = 1024*1024*1024 . 计算机算一下是46342.\n",
    "        k_max = 46341\n",
    "        k_mix = 0\n",
    "        k_mean = (k_mix + k_mean) // 2\n",
    "        while 1:\n",
    "            tmp = k_mean*k_mean\n",
    "            if tmp >= x and (k_mean-1)*(k_mean-1) < x:\n",
    "                return k_mean\n",
    "            if tmp > x:\n",
    "                k_max = k_mean\n",
    "                k_mean = (k_mix + k_max) // 2\n",
    "            else:\n",
    "                k_min = k_mean\n",
    "                k_mean = (k_mix + k_mean) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        i = 0\n",
    "        while (i+1)*(i+1) <= x:\n",
    "            i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l, r, a = 0, x, -1\n",
    "        while l <= r:\n",
    "            m = l + (r-l)//2\n",
    "            if m**2 <= x:\n",
    "                a=m\n",
    "                l = m+1\n",
    "            elif m**2 > x:\n",
    "                r = m - 1 \n",
    "        return a        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left, right, ans = 0, x//2 + 1, -1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if mid*mid <= x:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        i=1\n",
    "        if x==0:\n",
    "            return 0\n",
    "        else:\n",
    "            while i<=x:\n",
    "                if i**2<x:\n",
    "                    i+=1\n",
    "                elif i**2==x:\n",
    "                    break\n",
    "                elif i**2>x:\n",
    "                    i=i-1\n",
    "                    break\n",
    "            return i\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int (sqrt(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x <= 1:\n",
    "            return x \n",
    "        left = 1\n",
    "        right = math.floor(x/2)\n",
    "        while left < right:\n",
    "            mid = left +math.floor((right-left+1)/2)\n",
    "            if mid > x/mid :\n",
    "                right =mid-1\n",
    "            else :\n",
    "                left = mid\n",
    "\n",
    "        return left\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0 or x == 1:\n",
    "            return x\n",
    "        \n",
    "        left, right = 1, x // 2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            square = mid * mid\n",
    "            \n",
    "            if square <= x:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(math.sqrt(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0 or x == 1:\n",
    "            return x\n",
    "        \n",
    "        left, right = 1, x // 2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            square = mid * mid\n",
    "            \n",
    "            if square <= x:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "                \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0: return 0\n",
    "        res = int(x**0.5)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left = 0 \n",
    "        right = x\n",
    "        while left<=right: #<=左边界 \n",
    "            mid = (left+right)//2\n",
    "            if mid*mid == x:\n",
    "                return mid \n",
    "            if mid*mid >x:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left if left*left < x else left-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        \n",
    "        #return int(x**0.5)\n",
    "        \n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        while i * i <= x:\n",
    "            i += 1\n",
    "        return int(i - 1)\n",
    "        \"\"\"\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        c, x0 = float(x), float(x)\n",
    "        cnt = 0\n",
    "        while  True:\n",
    "            xi = 0.5 * (x0 + c/x0)\n",
    "            if abs(x0 - xi) < 1e-7:\n",
    "                break\n",
    "            x0 = xi\n",
    "            cnt += 1\n",
    "            #print(cnt, x0)\n",
    "        return int(x0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0 or x == 1:\n",
    "            return x\n",
    "        \n",
    "        left, right = 1, x // 2\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            square = mid * mid\n",
    "            \n",
    "            if square <= x:\n",
    "                left = mid \n",
    "            else:\n",
    "                right = mid - 1\n",
    "                \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l = 0\n",
    "        r = x\n",
    "        while (l <= r):\n",
    "            mid = (l + r) // 2\n",
    "            if mid * mid < x:\n",
    "                l = mid + 1\n",
    "            elif mid * mid > x:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        if x == 1:\n",
    "            return 1\n",
    "        left = 1\n",
    "        right = x\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "            if mid ** 2 == x:\n",
    "                return mid\n",
    "            elif mid ** 2 < x:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x < 0:\n",
    "            return -1\n",
    "        # elif x < 1:\n",
    "        #     return 0\n",
    "        # else:\n",
    "        #     pass\n",
    "        ##\n",
    "        left, right = 0, x\n",
    "        res = left\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            tmp = mid * mid\n",
    "            if tmp == x:\n",
    "                return mid \n",
    "            elif tmp < x:\n",
    "                res = mid \n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left, right = 0, x\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid * mid == x:\n",
    "                return mid\n",
    "            elif mid * mid < x:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left - 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left = 0\n",
    "        right = x\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid * mid < x:\n",
    "                left = mid + 1\n",
    "            elif mid * mid > x:\n",
    "                right = mid - 1\n",
    "            else: return mid\n",
    "        return left - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l, r, ans = 0, x, -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if mid * mid <= x:\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        return int(x**0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left = 0\n",
    "        right = x\n",
    "        mid = left + (right - left)//2\n",
    "        while left <= right:\n",
    "            if mid * mid < x:\n",
    "                left = mid + 1\n",
    "            elif mid * mid > x:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                return mid\n",
    "            mid = left + (right - left)//2\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        l, r, a = 0, x, -1\n",
    "        while l <= r:\n",
    "            m = l + (r-l)//2\n",
    "            if m**2 <= x:\n",
    "                a=m\n",
    "                l = m+1\n",
    "            elif m**2 > x:\n",
    "                r = m - 1 \n",
    "        return a        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        left, right = 1, x\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if mid * mid == x:\n",
    "                return mid\n",
    "            elif mid * mid > x:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x < 2:\n",
    "            return x\n",
    "    \n",
    "        left, right = 1, x // 2\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            square = mid * mid\n",
    "            if square == x:\n",
    "                return mid\n",
    "            elif square < x:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return right  # 注意，当循环结束时，right 是小于等于 x 的最大整数平方根"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x < 0:\n",
    "            return \n",
    "        elif x == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            pass\n",
    "        ##\n",
    "        c, x1 = x, 1\n",
    "        while True:\n",
    "            x2 = 0.5 * (x1 + c/x1)\n",
    "            if abs(x2 - x1) < 1e-7:\n",
    "                break\n",
    "            x1 = x2 \n",
    "        return int(x2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mySqrt(self, x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "\n",
    "        x0, c = float(x), float(x)\n",
    "        while True:\n",
    "            xi = (1/2)*(x0 + (c/x0))\n",
    "            if abs(xi - x0) < 1e-7:\n",
    "                break \n",
    "            x0 = xi\n",
    "        return int(x0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
